//
// Created by hay boy on 2022/6/20.
//
#include "DoublyLinkedList.h"

template<class T>
DoublyLinkedList<T>::DoublyLinkedList(){
    firstNode = lastNode = nullptr;
    listSize = 0;
}

template<class T>
DoublyLinkedList<T>::~DoublyLinkedList() {
    while(firstNode!=nullptr){
        BidirectionalNode<T>* nextNode = firstNode->next;
        delete firstNode;
        firstNode = nextNode;
    }
}

template<class T>
void DoublyLinkedList<T>::checkIndex(int theIndex) const {
    if(theIndex<0||theIndex>=listSize){
        ostringstream s;
        s<<"index = "<<theIndex<<" size = "<<listSize;
        throw illegalIndex(s.str());
    }
}

template<class T>
int DoublyLinkedList<T>::indexOf(const T &theElement) const {
    BidirectionalNode<T>* currentNode = firstNode;
    int index = 0;
    while(currentNode!=nullptr&&(*currentNode).element!=theElement){
        currentNode = currentNode->next;
        index++;
    }
    if(currentNode==nullptr){
        return -1;
    }else{
        return index;
    }
}

template<class T>
T &DoublyLinkedList<T>::get(int theIndex) const {
    checkIndex(theIndex);
    BidirectionalNode<T>* currentNode;
    if(theIndex<listSize/2){
        currentNode = firstNode;
        for(int i = 0;i<theIndex;i++){
            currentNode = currentNode->next;
        }
    }else{
        currentNode = lastNode;
        for(int i = 0;i<listSize-theIndex-1;i++){
            currentNode = currentNode->previous;
        }
    }
    return currentNode->element;
}

template<class T>
void DoublyLinkedList<T>::erase(int theIndex) {
    checkIndex(theIndex);
    BidirectionalNode<T>* deleteNode;
    if(theIndex==0){
        deleteNode = firstNode;
        firstNode = firstNode->next;
        firstNode->previous = nullptr;
        if(listSize==1){
            lastNode = nullptr;
        }
    }else if(theIndex==listSize-1){
        deleteNode = lastNode;
        lastNode = lastNode->previous;
        lastNode->next = nullptr;
    }else{
        BidirectionalNode<T>* p;
        if(theIndex<listSize/2){
            p = firstNode;
            for(int i = 0;i<theIndex-1;i++){
                p = p->next;
            }
            deleteNode = p->next;
            p->next->next->previous = p;
            p->next = p->next->next;
//            if(theIndex==Chain<T>::listSize-1){
//                lastNode = p;
//            }
        }else{
            p = lastNode;
            for(int i = 0;i<listSize-theIndex-2;i++){
                p = p->previous;
            }
            deleteNode = p->previous;
            p->previous->previous->next = p;
            p->previous = p->previous->previous;
        }
    }
    listSize--;
    delete deleteNode;
}

template<class T>
void DoublyLinkedList<T>::insert(int theIndex, const T &theElement) {
    if(theIndex<0||theIndex>listSize){
        ostringstream s;
        s<<"index = "<<theIndex<<" size = "<<listSize;
        throw illegalIndex(s.str());
    }
    if(theIndex==0){
        if(listSize==0){
            lastNode = firstNode = new BidirectionalNode<T>(theElement,nullptr,nullptr);
        }else{
            BidirectionalNode<T>* p = firstNode;
            firstNode = new BidirectionalNode<T>(theElement,nullptr,firstNode);
            p->previous = firstNode;
        }
    }else if(theIndex==listSize){
        lastNode->next = new BidirectionalNode<T>(theElement,lastNode,nullptr);
        lastNode = lastNode->next;
    }else{
        if(theIndex<listSize/2){
            BidirectionalNode<T>* p = firstNode;
            for(int i = 0;i<theIndex-1;i++){
                p = p->next;
            }
            BidirectionalNode<T>* p2 = p->next;
            p->next = new BidirectionalNode<T>(theElement,p,p->next);
            p2->previous = p->next;
        }else{
            BidirectionalNode<T>* p = lastNode;
            for(int i = 0;i<listSize-theIndex-2+1;i++){
                p = p->previous;
            }
            BidirectionalNode<T>* p2 = p->previous;
            p->previous = new BidirectionalNode<T>(theElement,p2,p);
            p2->next = p->previous;
        }
    }
    listSize++;
}

template<class T>
void DoublyLinkedList<T>::output(ostream &out) const {
    for(BidirectionalNode<T>* currentNode = firstNode;currentNode!=nullptr;currentNode=currentNode->next){
        out<<currentNode->element<<" ";
    }
}

template<class T>
void DoublyLinkedList<T>::clear() {
    while(firstNode!=nullptr){
        BidirectionalNode<T>* nextNode = firstNode->next;
        delete firstNode;
        firstNode = nextNode;
    }
    lastNode = nullptr;
    listSize = 0;
}

template<class T>
void DoublyLinkedList<T>::push_back(const T &theElement) {
    if(firstNode==nullptr){
        firstNode = lastNode = new BidirectionalNode<T>(theElement,nullptr,nullptr);
    }else{
        lastNode->next = new BidirectionalNode<T>(theElement,lastNode,nullptr);
        lastNode = lastNode->next;
    }
    listSize++;
}
template<class T>
ostream &operator<<(ostream &out, const DoublyLinkedList<T> &x) {
    x.output(out);
    return out;
}